package com.example.offer;

import java.util.*;

//todo offer中唯2不太会的 剑指 Offer 36. 二叉搜索树与双向链表 剑指 Offer 45. 把数组排成最小的数 剑指 Offer 41. 数据流中的中位数
// Offer 07. 重建二叉树  剑指 Offer 33. 二叉搜索树的后序遍历序列
public class Offer implements OfferInterface {
    public static void main(String[] args) {
        Offer offer = new Offer();
        offer.lengthOfLongestSubstring("null");
        Map<String, Object> map = new HashMap<>();
        map.put("2", 3);
        Map<String, Object> map2 = new HashMap<>();
        map2.put("2", 3);
        Set<String> strings = map.keySet();
        strings.removeAll(map2.keySet());
        System.out.println("1".compareTo("4324102"));
    }

    @Override
    public int translateNum(int num) {
        String src = String.valueOf(num);
        int p, q = 0, r = 1;
        for (int i = 0; i < src.length(); ++i) {
            p = q;
            q = r;
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            String pre = src.substring(i - 1, i + 1);
            if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
                r += p;
            }
        }
        return r;
    }

    @Override
    public int translateNum2(int num) {
        String s = String.valueOf(num);
        int length = s.length();
        if (length < 2) return length;
        char[] chars = s.toCharArray();
        int[] dp = new int[length];
        dp[0] = 1;
        for (int i = 1; i < length; i++) {
            dp[i] = dp[i - 1];
            int currentNum = 10 * (chars[i - 1] - '0') + chars[i] - '0';
            if (currentNum > 9 && currentNum < 26) {
                if (i - 2 < 0) {
                    dp[i]++;
                } else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[length - 1];
    }

    @Override
    public int lengthOfLongestSubstring(String s) {
        //if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0;
        //划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。
        int max = 0, start = -1;
        //使用哈希表map统计各字符最后一次出现的索引位置
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            //当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新:
            //当index>start时，start更新为当前的index,否则保持不变。
            //注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
            if (map.containsKey(tmp)) {
                start = Math.max(start, map.get(tmp));
            }
            //如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
            map.put(tmp, i);
            //i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。
            max = Math.max(max, i - start);
        }
        return max;
    }
}

class Solution43242 {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String x, String y) {
                return (x + y).compareTo(y + x);
            }
        });

        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }
}


